{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Process Restricted Friend Requests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: friendRequests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #处理含限制条件的好友请求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，表示网络上的用户数目。每个用户按从 <code>0</code> 到 <code>n - 1</code> 进行编号。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>restrictions</code> ，其中 <code>restrictions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 意味着用户 <code>x<sub>i</sub></code> 和用户 <code>y<sub>i</sub></code> <strong>不能</strong> 成为 <strong>朋友</strong> ，不管是 <strong>直接</strong> 还是通过其他用户 <strong>间接</strong> 。</p>\n",
    "\n",
    "<p>最初，用户里没有人是其他用户的朋友。给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>requests</code> 表示好友请求的列表，其中 <code>requests[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> 是用户 <code>u<sub>j</sub></code> 和用户 <code>v<sub>j</sub></code> 之间的一条好友请求。</p>\n",
    "\n",
    "<p>如果 <code>u<sub>j</sub></code> 和 <code>v<sub>j</sub></code> 可以成为 <strong>朋友</strong> ，那么好友请求将会 <strong>成功</strong> 。每个好友请求都会按列表中给出的顺序进行处理（即，<code>requests[j]</code> 会在 <code>requests[j + 1]</code> 前）。一旦请求成功，那么对所有未来的好友请求而言， <code>u<sub>j</sub></code> 和 <code>v<sub>j</sub></code> 将会 <strong>成为直接朋友 。</strong></p>\n",
    "\n",
    "<p>返回一个 <strong>布尔数组</strong> <code>result</code> ，其中元素遵循此规则：如果第 <code>j</code> 个好友请求 <strong>成功</strong><em> </em>，那么 <code>result[j]</code><em> </em>就是<em> </em><code>true</code><em> </em>；否则，为<em> </em><code>false</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>如果 <code>u<sub>j</sub></code> 和 <code>v<sub>j</sub></code> 已经是直接朋友，那么他们之间的请求将仍然&nbsp;<strong>成功</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]\n",
    "<strong>输出：</strong>[true,false]\n",
    "<strong>解释：\n",
    "</strong>请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。 \n",
    "请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1--2--0) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]\n",
    "<strong>输出：</strong>[true,false]\n",
    "<strong>解释：</strong>\n",
    "请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。 \n",
    "请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--2--1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]\n",
    "<strong>输出：</strong>[true,false,true,false]\n",
    "<strong>解释：\n",
    "</strong>请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。 \n",
    "请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。\n",
    "请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。 \n",
    "请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--4--3--1) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= restrictions.length &lt;= 1000</code></li>\n",
    "\t<li><code>restrictions[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= requests.length &lt;= 1000</code></li>\n",
    "\t<li><code>requests[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>j</sub>, v<sub>j</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>u<sub>j</sub> != v<sub>j</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [process-restricted-friend-requests](https://leetcode.cn/problems/process-restricted-friend-requests/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [process-restricted-friend-requests](https://leetcode.cn/problems/process-restricted-friend-requests/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1]]\\n[[0,2],[2,1]]', '3\\n[[0,1]]\\n[[1,2],[0,2]]', '5\\n[[0,1],[1,2],[2,3]]\\n[[0,4],[1,2],[3,1],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        # 2 <= n <= 1000\n",
    "        # 用并查集，先把关系复制一份，如果不行撤回就完事\n",
    "        p  = [i for i in range(n)]\n",
    "        \n",
    "        def find(node):\n",
    "            while p[node] != node:\n",
    "                p[node] = p[p[node]]\n",
    "                node = p[node]\n",
    "            return node\n",
    "        \n",
    "        def union(a, b):\n",
    "            root_a, root_b = find(a), find(b)\n",
    "            if root_a != root_b:\n",
    "                p[root_a] = root_b\n",
    "        \n",
    "        ans = []\n",
    "        for u, v in requests:\n",
    "            s = True\n",
    "            p_copy = p.copy()\n",
    "            union(u, v)\n",
    "            for i, j in restrictions:\n",
    "                if find(i) == find(j):\n",
    "                    s = False\n",
    "                    break\n",
    "\n",
    "            ans.append(s)\n",
    "            if not s:\n",
    "                p = p_copy.copy()\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        parent=list(range(n))\n",
    "        def find(x):\n",
    "            if parent[x]!=x:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            fx=find(x)\n",
    "            fy=find(y)\n",
    "            if fx!=fy:\n",
    "                parent[fy]=fx\n",
    "            return \n",
    "        ans=[]\n",
    "        for i,j in requests:\n",
    "            temp=list(parent)\n",
    "            if i<j:\n",
    "                union(i,j)\n",
    "            else :\n",
    "                union(j,i)\n",
    "            check=True\n",
    "            for x,y in restrictions:\n",
    "                if find(x)==find(y):\n",
    "                    check=False\n",
    "                    parent=temp\n",
    "                    break\n",
    "            ans.append(check)\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] == x: return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        ans = []\n",
    "        for a, b in requests:\n",
    "            r0, r1 = find(a), find(b)\n",
    "            if r0 == r1:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if r0 > r1: r0, r1 = r1, r0\n",
    "            valid = True\n",
    "            for re0, re1 in restrictions:\n",
    "                r_0, r_1 = find(re0), find(re1)\n",
    "                if r_0 > r_1: r_0, r_1 = r_1, r_0\n",
    "                if r_0 == r0 and r_1 == r1:\n",
    "                    valid = False\n",
    "                    break\n",
    "            ans.append(valid)\n",
    "            if valid:\n",
    "                fa[r1] = r0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "    def find(self,x):\n",
    "        if self.fa[x]!=x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return \n",
    "        self.fa[y] = x\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = UF(n)\n",
    "\n",
    "        ans = []\n",
    "        for a,b in requests:\n",
    "            if a>b:\n",
    "                a,b = b,a\n",
    "            a = uf.find(a)\n",
    "            b = uf.find(b)\n",
    "            for c,d in restrictions:\n",
    "                c = uf.find(c)\n",
    "                d = uf.find(d)\n",
    "                if (c == a and d == b) or (c==b and d==a):\n",
    "                    ans.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                uf.union(a,b)\n",
    "                ans.append(True)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.sz = [1] * n\n",
    "    def find(self,x):\n",
    "        if self.fa[x]!=x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return \n",
    "        if self.sz[y] > self.sz[x]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = UF(n)\n",
    "\n",
    "        ans = []\n",
    "        for a,b in requests:\n",
    "            if a>b:\n",
    "                a,b = b,a\n",
    "            a = uf.find(a)\n",
    "            b = uf.find(b)\n",
    "            for c,d in restrictions:\n",
    "                c = uf.find(c)\n",
    "                d = uf.find(d)\n",
    "                if (c == a and d == b) or (c==b and d==a):\n",
    "                    ans.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                uf.union(a,b)\n",
    "                ans.append(True)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.father = list(range(n))\n",
    "\n",
    "    def union(self, idx1, idx2):\n",
    "        self.father[self.find(idx2)] = self.find(idx1)\n",
    "    \n",
    "    def find(self, idx):\n",
    "        if self.father[idx] != idx:\n",
    "            self.father[idx] = self.find(self.father[idx])\n",
    "        return self.father[idx]\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        union = UnionFind(n)\n",
    "        res = []\n",
    "        for a, b in requests:\n",
    "            if union.find(a) == union.find(b):\n",
    "                res.append(True)\n",
    "                continue\n",
    "            flag = True\n",
    "            fa, fb = union.find(a), union.find(b)\n",
    "            for c, d in restrictions:\n",
    "                fc, fd = union.find(c), union.find(d)\n",
    "                if (fc == fa and fd == fb) or (fc == fb and fd == fa):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                union.union(a, b)\n",
    "            res.append(flag)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "    def find(self,x):\n",
    "        if self.fa[x]!=x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return \n",
    "        self.fa[y] = x\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = UF(n)\n",
    "\n",
    "        ans = []\n",
    "        for a,b in requests:\n",
    "            if a>b:\n",
    "                a,b = b,a\n",
    "            a = uf.find(a)\n",
    "            b = uf.find(b)\n",
    "            for c,d in restrictions:\n",
    "                if (uf.find(c) == a and uf.find(d) == b) or (uf.find(c)==b and uf.find(d)==a):\n",
    "                    ans.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                uf.union(a,b)\n",
    "                ans.append(True)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.sz = [1] * n\n",
    "    def find(self,x):\n",
    "        # if self.fa[x]!=x:\n",
    "        #     self.fa[x] = self.find(self.fa[x])\n",
    "        # return self.fa[x]\n",
    "        return self.find(self.fa[x]) if self.fa[x]!=x else x\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return \n",
    "        if self.sz[y] > self.sz[x]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = UF(n)\n",
    "\n",
    "        ans = []\n",
    "        for a,b in requests:\n",
    "            if a>b:\n",
    "                a,b = b,a\n",
    "            a = uf.find(a)\n",
    "            b = uf.find(b)\n",
    "            for c,d in restrictions:\n",
    "                c = uf.find(c)\n",
    "                d = uf.find(d)\n",
    "                if (c == a and d == b) or (c==b and d==a):\n",
    "                    ans.append(False)\n",
    "                    break\n",
    "            else:\n",
    "                uf.union(a,b)\n",
    "                ans.append(True)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa = [i for i in range(n)]\n",
    "        \n",
    "        ans = []\n",
    "        for [x, y] in requests:\n",
    "            fas = fa[:]\n",
    "            def find(x):\n",
    "                if x != fas[x]:\n",
    "                    fas[x] = find(fas[x])\n",
    "                return fas[x]\n",
    "            def merge(x, y):\n",
    "                fx, fy = find(x), find(y)\n",
    "                fas[fy] = fx\n",
    "            def isconn(x, y):\n",
    "                return find(x) == find(y)\n",
    "            merge(x, y)\n",
    "            n = True\n",
    "            for [x1, y1] in restrictions:\n",
    "                if isconn(x1, y1):\n",
    "                    n = False\n",
    "                    break\n",
    "            ans.append(n)\n",
    "            if n:\n",
    "                fa = fas[:]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    def find(self, x):\n",
    "        if x != self.p[x]:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y: return\n",
    "        if self.size[x] > self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.p[y] = x\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = DSU(n)\n",
    "        m = len(requests)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            x, y = uf.find(requests[i][0]), uf.find(requests[i][1])\n",
    "            if x != y:\n",
    "                check = True\n",
    "                for res in restrictions:\n",
    "                    u, v = uf.find(res[0]), uf.find(res[1])\n",
    "                    if (x == u and y == v) or (x == v and y == u):\n",
    "                        check = False\n",
    "                        break\n",
    "                if check:\n",
    "                    ans.append(True)\n",
    "                    uf.union(x, y)\n",
    "                else:\n",
    "                    ans.append(False)\n",
    "            else:\n",
    "                ans.append(True)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n)\n",
    "        ans = list()\n",
    "\n",
    "        for req in requests:\n",
    "            x, y = uf.findset(req[0]), uf.findset(req[1])\n",
    "            if x != y:\n",
    "                check = True\n",
    "                for res in restrictions:\n",
    "                    u, v = uf.findset(res[0]), uf.findset(res[1])\n",
    "                    if (x == u and y == v) or (x == v and y == u):\n",
    "                        check = False\n",
    "                        break\n",
    "                if check:\n",
    "                    ans.append(True)\n",
    "                    uf.unite(x, y)\n",
    "                else:\n",
    "                    ans.append(False)\n",
    "            else:\n",
    "                ans.append(True)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        g = [set() for _ in range(n)]\n",
    "        for a, b in restrictions:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "\n",
    "        parent = list(range(n))\n",
    "        size = [1] * n\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry:\n",
    "                return\n",
    "            parent[ry] = rx\n",
    "\n",
    "        ans = []\n",
    "        for a, b in requests:\n",
    "            ra, rb = find(a), find(b)\n",
    "            if ra == rb:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            rbb = []\n",
    "            for i in range(n):\n",
    "                if find(i) == rb:\n",
    "                    rbb.append(i)\n",
    "            union(a, b)\n",
    "            \n",
    "            if all(find(x) != find(y) for x, y in restrictions):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                for i in rbb:\n",
    "                    parent[i] = rb\n",
    "                ans.append(False)\n",
    "            \n",
    "\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    def __init__(self, key, parent=None):\n",
    "        self.key = key\n",
    "        self.parent = parent\n",
    "        self.length = 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        nodes = [DisjointSet(i) for i in range(n)]\n",
    "        restrict = [set() for _ in range(n)]\n",
    "        for r in restrictions:\n",
    "            restrict[r[0]].add(r[1])\n",
    "            restrict[r[1]].add(r[0])\n",
    "        ans = []\n",
    "\n",
    "        def find(node):\n",
    "            if node.parent is None:\n",
    "                return node\n",
    "            root = find(node.parent)\n",
    "            node.parent = root\n",
    "            return root\n",
    "\n",
    "        def union(node1, node2):\n",
    "            if node1.length < node2.length:\n",
    "                node1.parent = node2\n",
    "                node2.length += node1.length\n",
    "                restrict[node2.key] = restrict[node2.key].union(restrict[node1.key])\n",
    "            else:\n",
    "                node2.parent = node1\n",
    "                node1.length += node2.length\n",
    "                restrict[node1.key] = restrict[node1.key].union(restrict[node2.key])\n",
    "\n",
    "        for r in requests:\n",
    "            root0 = find(nodes[r[0]])\n",
    "            root1 = find(nodes[r[1]])\n",
    "            if root0 == root1:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            temp = set()\n",
    "            for v in restrict[root0.key]:\n",
    "                temp.add(find(nodes[v]).key)\n",
    "            restrict[root0.key] = restrict[root0.key].union(temp)\n",
    "            temp = set()\n",
    "            for v in restrict[root1.key]:\n",
    "                temp.add(find(nodes[v]).key)\n",
    "            restrict[root1.key] = restrict[root1.key].union(temp)\n",
    "            if root1.key in restrict[root0.key] or root0.key in restrict[root1.key]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                ans.append(True)\n",
    "                union(root0, root1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    def find(self, x):\n",
    "        if x != self.p[x]:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y: return\n",
    "        if self.size[x] > self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.p[y] = x\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = DSU(n)\n",
    "        m = len(requests)\n",
    "        ans = [0] * m\n",
    "        for i in range(m):\n",
    "            x, y = requests[i]\n",
    "            ufc = copy.deepcopy(uf)\n",
    "            ufc.union(x, y)\n",
    "            flag = True\n",
    "            for a, b in restrictions:\n",
    "                if ufc.connected(a, b):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                uf.union(x, y)\n",
    "            ans[i] = flag\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        def find(x):\n",
    "            if f[x]!=x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        f = list(range(n))\n",
    "        A = [1<<i for i in range(n)]\n",
    "        B = [0]*n\n",
    "        for u,v in restrictions:\n",
    "            B[u] |= 1<<v\n",
    "            B[v] |= 1<<u\n",
    "        res = []\n",
    "        for x,y in requests:\n",
    "            fx, fy = find(x), find(y)\n",
    "            if A[fx]&B[fy]:\n",
    "                res.append(False)\n",
    "            else:\n",
    "                res.append(True)\n",
    "                f[fx] = fy\n",
    "                A[fy] |= A[fx]\n",
    "                B[fy] |= B[fx]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    def find(self, x):\n",
    "        if x != self.p[x]:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y: return\n",
    "        if self.size[x] > self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.p[y] = x\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        uf = DSU(n)\n",
    "        m = len(requests)\n",
    "        ans = [0] * m\n",
    "        for i in range(m):\n",
    "            x, y = requests[i]\n",
    "            ufc = deepcopy(uf)\n",
    "            ufc.union(x, y)\n",
    "            flag = True\n",
    "            for a, b in restrictions:\n",
    "                if ufc.connected(a, b):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                uf.union(x, y)\n",
    "            ans[i] = flag\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\r\n",
    "        pa = list(range(n))\r\n",
    "        rs: list[set[int]] = [set() for _ in range(n)]\r\n",
    "        for u, v in restrictions:\r\n",
    "            rs[u].add(v)\r\n",
    "            rs[v].add(u)\r\n",
    "        \r\n",
    "        def find(i: int) -> int:\r\n",
    "            if pa[i] != i:\r\n",
    "                pa[i] = find(pa[i])\r\n",
    "            return pa[i]\r\n",
    "        \r\n",
    "        def join(r: list[int]) -> bool:\r\n",
    "            f, g = map(find, r)\r\n",
    "            if f == g: return True\r\n",
    "            if any(find(e) == g for e in rs[f]) or any(find(e) == f for e in rs[g]): return False\r\n",
    "            pa[f] = g\r\n",
    "            rs[g].update(rs[f])\r\n",
    "            return True\r\n",
    "        \r\n",
    "        return list(map(join, requests))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        forbid = defaultdict(set)\n",
    "\n",
    "        for x in restrictions:\n",
    "            forbid[x[0]].add(x[1])\n",
    "            forbid[x[1]].add(x[0])\n",
    "\n",
    "        fa = [i for i in range(n)]\n",
    "        tree = {i: {i} for i in range(n)}\n",
    "        res = []\n",
    "\n",
    "        def getroot(k: int) -> int:\n",
    "            return getroot(fa[k]) if fa[k] != k else k\n",
    "\n",
    "        def canReach(i:int,j:int)->int:\n",
    "            if len(tree[i])<len(tree[j]):\n",
    "                for x in tree[i]:\n",
    "                    if x in forbid[j]:\n",
    "                        return False\n",
    "            else:\n",
    "                for x in tree[j]:\n",
    "                    if x in forbid[i]:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        for x in requests:\n",
    "            a, b = getroot(x[0]), getroot(x[1])\n",
    "            if a==b:\n",
    "                res.append(True)\n",
    "                continue\n",
    "            if canReach(a,b):\n",
    "                fa[a] = b\n",
    "                forbid[b] = forbid[b].union(forbid[a])\n",
    "                tree[b] = tree[b].union(tree[a])\n",
    "                del forbid[a]\n",
    "                del tree[a]\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa=list(range(n))\n",
    "        rset=[set() for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            rset[x].add(y)\n",
    "            rset[y].add(x)\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        ans=[]\n",
    "        for x,y in requests:\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if xfa==yfa:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if xfa in rset[yfa]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                rset[yfa] |=rset[xfa]\n",
    "                for k in rset[yfa]:\n",
    "                    # rset[k].add(xfa)\n",
    "                    rset[k].add(yfa)\n",
    "                ans.append(True)\n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        # fa=list(range(n))\n",
    "        # def find(x):\n",
    "        #     if fa[x]!=x:\n",
    "        #         fa[x]=find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # rMatrix=[[0]*n for _ in range(n)]\n",
    "        # for x,y in restrictions:\n",
    "        #     rMatrix[x][y]=1\n",
    "        #     rMatrix[y][x]=1\n",
    "\n",
    "        # ans=[True]*len(requests)\n",
    "        # for i,(x,y) in enumerate(requests):\n",
    "        #     xfa,yfa=find(x),find(y)\n",
    "        #     if xfa==yfa:continue\n",
    "        #     if rMatrix[xfa][yfa]:\n",
    "        #         ans[i]=False\n",
    "        #     else:\n",
    "        #         fa[xfa]=yfa\n",
    "        #         for k in range(n):\n",
    "        #             rMatrix[yfa][k] |=rMatrix[xfa][k]\n",
    "        #             rMatrix[k][yfa] |=rMatrix[k][xfa]\n",
    "        # # print(rMatrix)\n",
    "        # return ans\n",
    "\n",
    "        fa=list(range(n))\n",
    "        rset=[set() for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            rset[x].add(y)\n",
    "            rset[y].add(x)\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        ans=[]\n",
    "        for x,y in requests:\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if xfa==yfa:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if xfa in rset[yfa] or yfa in rset[xfa]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                rset[yfa] |=rset[xfa]\n",
    "                for k in rset[yfa]:\n",
    "                    # rset[k].add(xfa)\n",
    "                    rset[k].add(yfa)\n",
    "                ans.append(True)\n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        # restrictSet=set(restrictions)\n",
    "        # rMatrix=[[1]*n for _ in range(n)]\n",
    "        # for x,y in restrictions:\n",
    "        #     rMatrix[x][y]=0\n",
    "        #     rMatrix[y][x]=0\n",
    "        # ans=[]\n",
    "        # for x,y in requests:\n",
    "        #     if rMatrix[x][y]==0:\n",
    "        #         ans.append(False)\n",
    "        #     else:\n",
    "        #         for k in range(n):\n",
    "        #             if rMatrix[x][k]!=rMatrix[y][k]: \n",
    "        #             # t=rMatrix[x][k]&rMatrix[y][k]\n",
    "        #                 rMatrix[x][k]=rMatrix[y][k]=0\n",
    "        #                 rMatrix[k][x]=rMatrix[k][y]=0\n",
    "        #         ans.append(True)\n",
    "        # print(rMatrix)\n",
    "        # return ans\n",
    "        fa=list(range(n))\n",
    "        rset=[set() for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            rset[x].add(y)\n",
    "            rset[y].add(x)\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        ans=[]\n",
    "        for x,y in requests:\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if xfa==yfa:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if xfa in rset[yfa] or yfa in rset[xfa]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                rset[yfa] |=rset[xfa]\n",
    "                for k in rset[yfa]:\n",
    "                    rset[k].add(xfa)\n",
    "                    rset[k].add(yfa)\n",
    "                ans.append(True)\n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa=list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        rMatrix=[[0]*n for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            rMatrix[x][y]=1\n",
    "            rMatrix[y][x]=1\n",
    "\n",
    "        ans=[]\n",
    "        for x,y in requests:\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if rMatrix[xfa][yfa]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                for k in range(n):\n",
    "                    rMatrix[yfa][k] |=rMatrix[xfa][k]\n",
    "                    rMatrix[k][yfa] |=rMatrix[k][xfa]\n",
    "                ans.append(True)\n",
    "        # print(rMatrix)\n",
    "        return ans\n",
    "\n",
    "        # fa=list(range(n))\n",
    "        # rset=[set() for _ in range(n)]\n",
    "        # for x,y in restrictions:\n",
    "        #     rset[x].add(y)\n",
    "        #     rset[y].add(x)\n",
    "        # def find(x):\n",
    "        #     if fa[x]!=x:\n",
    "        #         fa[x]=find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # ans=[]\n",
    "        # for x,y in requests:\n",
    "        #     xfa,yfa=find(x),find(y)\n",
    "        #     if xfa==yfa:\n",
    "        #         ans.append(True)\n",
    "        #         continue\n",
    "        #     if xfa in rset[yfa] or yfa in rset[xfa]:\n",
    "        #         ans.append(False)\n",
    "        #     else:\n",
    "        #         fa[xfa]=yfa\n",
    "        #         rset[yfa] |=rset[xfa]\n",
    "        #         for k in rset[yfa]:\n",
    "        #             rset[k].add(xfa)\n",
    "        #             rset[k].add(yfa)\n",
    "        #         ans.append(True)\n",
    "        # return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa=list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        rMatrix=[[0]*n for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            rMatrix[x][y]=1\n",
    "            rMatrix[y][x]=1\n",
    "\n",
    "        ans=[True]*len(requests)\n",
    "        for i,(x,y) in enumerate(requests):\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if xfa==yfa:continue\n",
    "            if rMatrix[xfa][yfa]:\n",
    "                ans[i]=False\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                for k in range(n):\n",
    "                    rMatrix[yfa][k] |=rMatrix[xfa][k]\n",
    "                    rMatrix[k][yfa] |=rMatrix[k][xfa]\n",
    "        # print(rMatrix)\n",
    "        return ans\n",
    "\n",
    "        # fa=list(range(n))\n",
    "        # rset=[set() for _ in range(n)]\n",
    "        # for x,y in restrictions:\n",
    "        #     rset[x].add(y)\n",
    "        #     rset[y].add(x)\n",
    "        # def find(x):\n",
    "        #     if fa[x]!=x:\n",
    "        #         fa[x]=find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # ans=[]\n",
    "        # for x,y in requests:\n",
    "        #     xfa,yfa=find(x),find(y)\n",
    "        #     if xfa==yfa:\n",
    "        #         ans.append(True)\n",
    "        #         continue\n",
    "        #     if xfa in rset[yfa] or yfa in rset[xfa]:\n",
    "        #         ans.append(False)\n",
    "        #     else:\n",
    "        #         fa[xfa]=yfa\n",
    "        #         rset[yfa] |=rset[xfa]\n",
    "        #         for k in rset[yfa]:\n",
    "        #             rset[k].add(xfa)\n",
    "        #             rset[k].add(yfa)\n",
    "        #         ans.append(True)\n",
    "        # return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet():\r\n",
    "    def __init__(self, n: int):\r\n",
    "        self.parent = [i for i in range(n)]\r\n",
    "        self.blacklist = [set() for i in range(n)]\r\n",
    "        self.members = [{i} for i in range(n)]\r\n",
    "    def find(self, x: int) -> int:\r\n",
    "        if x != self.parent[x]:\r\n",
    "            new_parent = self.find(self.parent[x])\r\n",
    "            self.parent[x] = new_parent\r\n",
    "            self.blacklist[new_parent] |= self.blacklist[x]\r\n",
    "            self.members[new_parent] |= self.members[x]\r\n",
    "        return self.parent[x]\r\n",
    "    def union(self, x: int, y: int):\r\n",
    "        px, py = self.find(x), self.find(y)\r\n",
    "        if (self.blacklist[px] & self.members[py]) or (self.blacklist[py] & self.members[px]):\r\n",
    "            return False\r\n",
    "        else:\r\n",
    "            self.parent[py] = px\r\n",
    "            self.blacklist[px] |= self.blacklist[py]\r\n",
    "            self.members[px] |= self.members[py]\r\n",
    "            return True\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\r\n",
    "        u = UnionSet(n)\r\n",
    "        for a, b in restrictions:\r\n",
    "            u.blacklist[a].add(b)\r\n",
    "            u.blacklist[b].add(a)\r\n",
    "        return [u.union(a, b) for a, b in requests]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        include = [set([]) for _ in range(n)]\n",
    "        forbid = [set([]) for _ in range(n)]\n",
    "        root = [i for i in range(n)]\n",
    "        for u, v in restrictions:\n",
    "            include[u].add(u)\n",
    "            include[v].add(v)\n",
    "            forbid[u].add(v)\n",
    "            forbid[v].add(u)\n",
    "        def find(x):\n",
    "            if root[x] != x:\n",
    "                return find(root[x])\n",
    "            return x\n",
    "        def join(x, y):\n",
    "            u, v = find(x), find(y)\n",
    "            if forbid[u] & include[v] or forbid[v] & include[u]:\n",
    "                return False\n",
    "            else:\n",
    "                root[v] = u\n",
    "                forbid[u] = forbid[u] | forbid[v]\n",
    "                include[u] = include[u] | include[v]\n",
    "                return True\n",
    "        ans = []\n",
    "        for x, y in requests:\n",
    "            ans.append(join(x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class UF:\n",
    "    def __init__(self, n,restrictions) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.g = [set() for _ in range(n)]\n",
    "        self.z = [{i} for i in range(n)]\n",
    "        for u,v in restrictions:\n",
    "            self.g[u].add(v)\n",
    "            self.g[v].add(u)\n",
    "    def find(self,x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self,x,y):\n",
    "        x,y = self.find(x),self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        self.parent[x] = y\n",
    "        self.z[y].update(self.z[x])\n",
    "        self.g[y].update(self.g[x])\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        ans = [False] * len(requests)\n",
    "        uf = UF(n,restrictions)\n",
    "        for i,(u,v) in enumerate(requests):\n",
    "            q = uf.g[uf.find(u)].intersection(uf.z[uf.find(v)])\n",
    "            if not len(q):\n",
    "                ans[i] = True\n",
    "                uf.merge(u,v)\n",
    "        return ans\n",
    "\n",
    "s = Solution()\n",
    "s.friendRequests(3,[[0,1]], [[0,2],[2,1]])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        UF = UnionFind(n)\n",
    "        for u, v in restrictions:\n",
    "            UF.restrict[u].add(v)\n",
    "            UF.restrict[v].add(u)\n",
    "\n",
    "        ans = [UF.unionSet(*r) for r in requests]\n",
    "        return ans \n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))    \n",
    "        self.restrict = [set() for _ in range(n)] \n",
    "        self.friends =  [set([i]) for i in range(n)]         \n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            self.restrict[self.parents[i]] |= self.restrict[i]\n",
    "            self.friends[self.parents[i]] |= self.friends[i]\n",
    "            return self.parents[i]\n",
    "        \n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        if (self.restrict[ip] & self.friends[jp]) or (self.restrict[jp] & self.friends[ip]):\n",
    "            return False \n",
    "        else:\n",
    "            self.parents[ip] = jp\n",
    "            self.restrict[jp] |= self.restrict[ip]\n",
    "            self.friends[jp] |= self.friends[ip]\n",
    "            return True \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class UF:\n",
    "    def __init__(self, n,restrictions) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.g = [set() for _ in range(n)]   # 该集合不能包含哪些元素\n",
    "        self.z = [{i} for i in range(n)]     # 该集合包含哪些元素\n",
    "        for u,v in restrictions:\n",
    "            self.g[u].add(v)\n",
    "            self.g[v].add(u)\n",
    "    def find(self,x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self,x,y):\n",
    "        x,y = self.find(x),self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        self.parent[x] = y\n",
    "        self.z[y].update(self.z[x])\n",
    "        self.g[y].update(self.g[x])\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        ans = [False] * len(requests)\n",
    "        uf = UF(n,restrictions)\n",
    "        for i,(u,v) in enumerate(requests):\n",
    "            if not uf.g[uf.find(u)].intersection(uf.z[uf.find(v)]):\n",
    "                ans[i] = True\n",
    "                uf.merge(u,v)\n",
    "        return ans\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class UF:\n",
    "    def __init__(self, n,restrictions) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.g = [set() for _ in range(n)]\n",
    "        self.z = [{i} for i in range(n)]\n",
    "        for u,v in restrictions:\n",
    "            self.g[u].add(v)\n",
    "            self.g[v].add(u)\n",
    "    def find(self,x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self,x,y):\n",
    "        x,y = self.find(x),self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        self.parent[x] = y\n",
    "        self.z[y].update(self.z[x])\n",
    "        self.g[y].update(self.g[x])\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        ans = [False] * len(requests)\n",
    "        uf = UF(n,restrictions)\n",
    "        for i,(u,v) in enumerate(requests):\n",
    "            if not uf.g[uf.find(u)].intersection(uf.z[uf.find(v)]):\n",
    "                ans[i] = True\n",
    "                uf.merge(u,v)\n",
    "        return ans\n",
    "\n",
    "s = Solution()\n",
    "s.friendRequests(3,[[0,1]], [[0,2],[2,1]])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n",
    "        fa=list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        friend=[set([i]) for i in range(n)]\n",
    "        enemy=[set() for _ in range(n)]\n",
    "        for x,y in restrictions:\n",
    "            enemy[x].add(y)\n",
    "            enemy[y].add(x)\n",
    "\n",
    "        ans=[]\n",
    "        for x,y in requests:\n",
    "            xfa,yfa=find(x),find(y)\n",
    "            if xfa==yfa:\n",
    "                ans.append(True)\n",
    "                continue\n",
    "            if friend[xfa]&enemy[yfa]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                fa[xfa]=yfa\n",
    "                friend[yfa] |= friend[xfa]\n",
    "                enemy[yfa] |=enemy[xfa]\n",
    "                # for k in enemy[yfa]:\n",
    "                #     enemy[k].add(yfa)\n",
    "                ans.append(True)\n",
    "        return ans      "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
